#include <iostream>

template<typename DT>
class BasicNode
{
private:
    DT element;
    BasicNode *left;
    BasicNode *right;

public:
  
  DT getElement() const  {}
  DT setElement( DT _val )  {}

  Node(DT _val){}
    
  BasicNode& getLeft(){}
  BasicNode& getRight(){}
  void setLeft(){}
  void setright(){}
};



template<typename DT>
class BinaryTree
{
public:
  BinaryTree(){}
  BinaryTree( const & BinaryTree<DT> t) {}
  ~BinaryTree(){}

  virtual void insert( const & DT){}
  virtual void remove( const & DT){}
  void output(){}

  bool isEmpty() const {}      //实现挺简单的，直接在public就实现了
  viod makeEmpty(){}

  
private:
  class Node : public BasicNode<DT>
  {};
  Node root;

  void insert( const & DT, Node * & t){}   
  void remove( const & DT, Node * & t){}

  void makeEmpty( Node * & t ){}
  bool search( const & DT, Node * & t){}
  Node output (const Node * & t){} const  //这个输出的类型不定，可能是打印，可能是以字符串提交给另一个文件等等，但是一个合格基本的容器应该有把它存储的数据输出的功能
  
    };



template<typename DT>
class BinarySearchTree : public BinaryTree<DT>
{
public:
  virtual void insert( const & DT){}
  virtual void remove( const & DT){}

  bool search( const & DT){}
  DT findMin(){}
  DT findMax(){}

private:
  //因为搜索二叉树加上了顺序，所以这里的插入和删除的方式会和BinaryTree有区别，需要重写
  void insert( const & DT, Node * & t){}   
  void remove( const & DT, Node * & t){}

  bool search( const & DT, Node * & t){}
  Node finaMin( Node * & t){}
  Node findMax( Node * & t){}
};



template<typename DT>
class AVLTree : public BinarySearchTree<DT>
{
public:
  //AVL树在进行动态操作的过程结点变化，可能需要对树做出调整，故插入和删除需要重写
   void insert( const & DT){}
   void remove( const & DT){}

private:
  class Node
  {
  public:
    //AVL树在保证平衡时需要知道结点的子树的高度，故添加。随之，结点初始化的逻辑需要更改。
    int height;
    Node(DT _val){}
    
  };
  
  void insert( const & DT, Node * & t){}   
  void remove( const & DT, Node * & t){}
  
  void balance( Node & t){}
};



template<typename DT>
class SplayTree : public BinarySearchTree<DT>
{
public:
  //伸展树的每次动态操作都需要调整树，故需要重写
  void insert( const & DT){}
  void remove( const & DT){}

private:
  void insert( const & DT, Node * & t){}   
  void remove( const & DT, Node * & t){}
  
  void Splay( Node & t){}
  
};
